package com.my.algorithmlearning.leetcode;

import org.springframework.util.Assert;

/**
 * @ClassName Medium_53_MaxSubArray
 * @Description 题目：https://leetcode.cn/problems/maximum-subarray/?favorite=2cktkvj
 * 题解：https://leetcode.cn/problems/maximum-subarray/solution/zhong-deng-53-zui-da-zi-shu-zu-he-dong-t-g661/
 * @Author wanghaiwei
 * @Date 2023/2/28 16:30
 */
public class Medium_53_MaxSubArray {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(Math.max(nums[0], nums[1]), nums[0] + nums[1]);
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int maxValue = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            maxValue = Math.max(maxValue, dp[i]);
        }
        return maxValue;
    }

    public static void main(String[] args) {
        Medium_53_MaxSubArray solution = new Medium_53_MaxSubArray();
        int result = solution.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
        Assert.isTrue(result == 6, "[-2,1,-3,4,-1,2,1,-5,4]计算错误，预期：6，实际:" + result);

        result = solution.maxSubArray(new int[]{1});
        Assert.isTrue(result == 1, "[1]计算错误，预期：6，实际:" + result);

        result = solution.maxSubArray(new int[]{5, 4, -1, 7, 8});
        Assert.isTrue(result == 23, "[5,4,-1,7,8]计算错误，预期：23，实际:" + result);

        result = solution.maxSubArray(new int[]{-2, -3, -1});
        Assert.isTrue(result == -1, "[-2,-3,-1]计算错误，预期：-1，实际:" + result);

        result = solution.maxSubArray(new int[]{-1, 1, 2, 1});
        Assert.isTrue(result == 4, "[-1,1,2,1]计算错误，预期：4，实际:" + result);

        result = solution.maxSubArray(new int[]{3, -2, -3, -3, 1, 3, 0});
        Assert.isTrue(result == 4, "[3,-2,-3,-3,1,3,0]计算错误，预期：4，实际:" + result);
    }
}
